# -*- encoding: utf-8 -*-

"""
------------------------------------------
@File       : 5_priority_queue.py
@Author     : maixiaochai
@Email      : maixiaochai@outlook.com
@CreatedOn  : 2021/12/27 15:13
------------------------------------------
    优先队列，最大优先队列
"""


class PriorityQueue:
    def __init__(self):
        self.array = []

    @property
    def size(self):
        return len(self.array)

    def enqueue(self, element):
        self.array.append(element)
        self.up_adjust()

    def dequeue(self):
        if not self.array:
            raise Exception("队列为空！")

        # 这里没有直接使用 self.pop()，因为还进行了额外的步骤：将最后一个元素移到顶端
        head = self.array[0]
        self.array[0] = self.array[self.size - 1]

        # 源码中，作者对array的长度进行了手动加减，没有采取 pop的方式,我这里的对self.size的处理方式与其不同，但效果相同
        # 这里这么写，是因为剩最后一个元素的时候，如果再pop列表就空了，后边 down_adjust中通过索引取数的操作就会报错
        if self.size >= 2:
            self.array.pop()

        self.down_adjust()

        return head

    def up_adjust(self):
        """
            向上调整，当插入新元素的时候会需要
        """
        # 因为插入了新元素并且作为最后一个节点，所以要向上调整
        child_index = self.size - 1
        parent_index = (child_index - 1) // 2

        temp = self.array[child_index]

        while child_index > 0 and temp > self.array[parent_index]:
            self.array[child_index] = self.array[parent_index]
            child_index = parent_index
            parent_index = (child_index - 1) // 2

        # 这里注意，很容易写错，应该是child_index,也就是旧的parent_index，即应该被换的parent
        self.array[child_index] = temp

    def down_adjust(self):
        """
            向下调整，当出队之后，最后一个元素临时补到第一个元素，此时需要重新向下调整
        """
        parent_index = 0
        temp = self.array[parent_index]
        # 先用其中一个孩子（这里是左孩子），后边会和另一个孩子（这里应为右孩子）作比较
        child_index = parent_index * 2 + 1

        # 这里为什么是child_index < self.size？因为考虑边界问题，左孩子可能就是最后一个节点
        while child_index < self.size:
            # 这里同样考虑边界，child + 1是右孩子，右孩子的索引小于self.size，翻译一下就是右孩子最多是最后一个元素(索引self.size - 1)
            # 如果存在右孩子，并且右孩子的值大于左孩子，则定位到右孩子
            if child_index + 1 < self.size and self.array[child_index] < self.array[child_index + 1]:
                child_index += 1

            # 如果parent值比孩子节点中的最大的都大，则不用换了，直接跳出
            if temp > self.array[child_index]:
                break

            self.array[parent_index] = self.array[child_index]
            parent_index = child_index
            child_index = parent_index * 2 + 1

        # 这里注意，很容易写错，应该是parent_index,也就是旧的 child_index,即应该被换的child
        self.array[parent_index] = temp


def demo():
    queue = PriorityQueue()

    elements = [3, 5, 10, 2, 7]
    for i in elements:
        queue.enqueue(i)

    print(f'将插入的数据：{queue.array}')
    print('-' * 50)
    print('优先队列出队：')

    for i in range(len(elements)):
        print(queue.dequeue())


if __name__ == '__main__':
    demo()
